package org.zhs.linear;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.function.Consumer;

/**
 * @Author: zhs
 * @Date: 2024/5/1 08:32
 * @Version: 1.0
 * @Description: 这个链表不支持NULL作为值,
 * 实现了get、add、remove、foreach
 * 至于set方法就不实现了，因为很简单
 */
public class MyLinkedList<E> {

    /**
     * 头节点
     */
    private Node<E> head;

    /**
     * 尾节点
     */
    private Node<E> last;

    /**
     * 实际长度
     */
    private int size;

    public MyLinkedList() {
        this.size = 0;
    }

    /**
     * 获取头节点
     *
     * @return
     */
    public E getFirst() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        return head.data;
    }

    /**
     * 获取尾节点
     *
     * @return
     */
    public E getLast() {
        if (last == null) {
            throw new NoSuchElementException();
        }
        return last.data;
    }

    /**
     * 获取指定下标的元素
     *
     * @param index
     * @return
     */
    public E get(int index) {
        if (!checkPositionIndex(index)) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return getNode(index).data;
    }

    /**
     * 追加的形式
     *
     * @param data
     */
    public void add(E data) {
        if (data == null) {
            throw new NullPointerException();
        }
        addLast(data);
    }

    /**
     * 在指定元素之前的添加
     *
     * @param index
     * @param data
     */
    public void add(int index, E data) {
        if (data == null) {
            throw new NullPointerException();
        }
        addBefore(data, getNode(index));
    }


    /**
     * 插入尾节点
     *
     * @param data
     */
    public void addLast(E data) {
        if (data == null) {
            throw new NullPointerException();
        }
        // 尾插入，尾插入只需要直接获取当前尾节点就可以设置
        Node<E> oldLast = last;
        Node<E> newNode = new Node<>(data, oldLast, null);
        // 先设置尾节点
        last = newNode;
        // 判断上一个节点是否为空，如果是空的话，那么就是一个空的链表，设置头节点
        if (oldLast == null) {
            head = newNode;
        } else {
            // 如果上一个不为空，则设置上一个节点的尾节点为当前节点
            oldLast.next = newNode;
        }
        size++;
    }

    /**
     * 在指定索引的节点前插入新的节点
     *
     * @param data
     * @param node
     */
    private void addBefore(E data, Node<E> node) {
        // 获取指定节点的前一个
        Node<E> oldNodePrev = node.prev;
        // 创建一个新的节点
        Node<E> newNode = new Node<>(data, oldNodePrev, node);
        if (oldNodePrev == null) {
            head = newNode;
        } else {
            oldNodePrev.next = newNode;
        }
        size++;
    }

    /**
     * 删除头节点
     *
     * @return
     */
    public E removeFirst() {
        if (head == null) {
            throw new NoSuchElementException();
        }

        return unlink(head);
    }


    /**
     * 删除尾节点
     *
     * @return
     */
    public E removeLast() {
        if (last == null) {
            throw new NoSuchElementException();
        }

        return unlink(last);
    }

    /**
     * 删除指定元素
     * 不支持NULL
     * 实际的jdk中是支持的
     *
     * @param o
     * @return
     */
    public boolean remove(Object o) {
        if (o == null) {
            throw new NullPointerException();
        }

        // 循环的终止条件为next = null, 表示已经遍历到尾节点
        for (Node<E> x = head; x != null; x = x.next) {
            if (o.equals(x.data)) {
                unlink(x);
                return true;
            }
        }
        return false;
    }

    E unlink(Node<E> node) {
        // 如果删除的节点是头节点
        if (node == head) {
            final E data = node.data;
            final Node<E> next = node.next;
            // 将节点的下一个节点清空, 将节点的数据清空
            node.next = null;
            node.data = null;
            // 如果下一个节点是空，则该头节点也是尾节点，就将尾节点也清空
            if (next == null) {
                last = null;
            } else {
                // 将下一个节点的头节点清空，并设置为头节点
                next.prev = null;
                head = next;
            }
            size--;
            return data;
        }
        // 如果删除的是尾节点
        else if (node == last) {
            final E data = node.data;
            final Node<E> prev = node.prev;
            // 将节点的前一节点清空，然后清空数据
            node.prev = null;
            node.data = null;
            // 如果前一个节点是null，表示当前节点是尾节点也是头节点，就将头节点也清空
            if (prev == null) {
                head = null;
            } else {
                // 将前一个节点的尾节点清空，并设置尾节点
                prev.next = null;
                last = prev;
            }
            size--;
            return data;
        }
        // 如果是指定元素删除
        else {
            final Node<E> prev = node.prev;
            final Node<E> next = node.next;
            final E data = node.data;
            // 清空自己的属性
            node.prev = null;
            node.next = null;
            node.data = null;
            // 将前一个节点的尾节点设置成自己的尾节点， 将自己的尾节点设置成前一个节点的尾节点
            prev.next = next;
            next.prev = prev;
            size--;

            return data;
        }
    }


    /**
     * 获取指定索引的节点
     * *********** 这里的代码是JDK中的原有的代码，很是巧妙，可以仔细分析在循环取出指定索引下标时的循环代码
     *
     * @param index
     * @return
     */
    private Node<E> getNode(int index) {
        // 判断当前索引是否合规（是否越界）
        if (!checkPositionIndex(index)) {
            throw new ArrayIndexOutOfBoundsException();
        }

        // 在这里来说，它们的意义一样 size >> 1 == size / 2
        // 1.这里首先判断指定的下标是大于size的一半
        // 2.如果小于一半就从0开始循环到index（正向）而且注意是到index因为实际上这个数据存在的范围就是0 到index，不需要遍历到size/2
        // 3.如果大于一半就从size-1开始循环到index（反向），相反的这里是size-1到index。也不需要遍历到size/2
        // 4.（像不像一个二分查找）
        // 5.如果是正向遍历就获取头节点，然后一直获取next直到index; 如果是反向遍历就获取尾节点，然后一直获取prev直到index
        if (index < (size >> 1)) {
            // 获取到头节点
            Node<E> x = head;
            //
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            // 获取到尾节点
            Node<E> x = last;
            //
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    private boolean checkPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    /**
     * 获取长度
     */
    public int size() {
        return this.size;
    }


    /**
     * 实现foreach循环
     *
     * @param consumer
     */
    public void foreach(Consumer<E> consumer) {
        for (Node<E> x = head; x != null; x = x.next) {
            consumer.accept((E) x.data);
        }
    }


    /**
     * 节点对象
     *
     * @param <E>
     */
    private static class Node<E> {

        /**
         * 当前数据
         */
        E data;

        /**
         * 上一个节点
         */
        Node<E> prev;

        /**
         * 下一个节点
         */
        Node<E> next;

        Node(E data, Node<E> prev, Node<E> next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

    public Iterator<E> iterator(){
        return new Itr(0);
    }

    public Iterator<E> iterator(int index){
        return new Itr(index);
    }

    /**
     * 实现迭代器
     */
    private class Itr implements Iterator<E> {

        //上次返回的值
        private Node<E> preReturn;
        // 当前节点
        private Node<E> node;

        public Itr(int index){
            node = getNode(index);
            preReturn = node;
        }

        @Override
        public boolean hasNext() {
            return preReturn.next != null;
        }

        @Override
        public E next() {
            if(!hasNext()){
                throw new NoSuchElementException();
            }
            preReturn = node;
            node = node.next;
            return preReturn.data;
        }

        @Override
        public void remove() {
            MyLinkedList.this.remove(node);
        }
    }


    @Override
    public String toString() {
        List<E> list = new ArrayList<>();
        for (Node<E> x = head; x != null; x = x.next) {
            list.add(x.data);
        }
        return list.toString();
    }
}
